One-way transformations have been studied for a variety of possible application, including encryption, authentication, information coding, computer password protection, and unique signal monitoring in weapon systems.
Briefly, a one-way transformation is easy to accomplish, but difficult to invert. A more complete definition is as follows:
a one-way transform, or function, f, is a function such that for any argument x in the domain of f, it is computationally straightforward to compute y=f(x), but for almost all y in the range of f, it is computationally difficult to compute x determinstically. That is, it is difficult to obtain the inverse transform of y.
Ease and difficulty can be measured in terms of computational requirements in time and equipment.
The one-way function definition specifies that deriving x from y must be computationally difficult for almost all y. This means that for a transform to be useful, it need not depend on 100 percent nonivertibility. It is quite possible that a transform would be used in such a way as to avoid the cases for which it was known to be invertible. For an example, the inverse of exponentiation is relatively difficult in general (e.g., using logarithms), but for some cases (e.g., squaring) the inverse is solvable by simple functions.
A final elaboration is necessary because of the last word in the definition, "deterministically." This accounts for a common extension of the reference usage to allow for inversion difficulty based on a large population being mapped to a small population. Thus, a many-to-one mapping may inhibit inversion (even though the inversion is straightforward) if the potential population for x is large. Thus, x.sub.1 is the input to the transformation, but f(x.sub.1)=y=f(x.sub.i), where x.sub.i represents a large population in addition to x.sub.1.
One-way transformations are thus applicable in various fields, including encryption, message authentication, PIN protection, password protection and accident protection, for example.
In encryption the transformation is generally used to disguise information; the inversion difficulty is relied upon to prevent cryptanalysis. An intended recipient of the information must, however, be readily able to perform the inversion. This is accomplished by privileged knowledge (such as decryption key or analogous "trapdoor" information). Applications of message authentication include electronic banking transactions, which commonly carry a relatively short "authenticator" that is a transformation dependent on the entire transaction. The intent is to easily create an authenticator, but to make it difficult to deduce (short of trial and error) any other data/authenticator pairs. This discourages tampering with the data. In this case, the transformation must be protected from an adversary.
Encryption, or transformation, is also used in PIN protection. Bank cards usually carry encoded PINs on the magnetic stripe of the card in order to permit "off-line" use when the central computer is unavailable. Both secrecy and authentication are desirable. Knowing the contents of the magnetic stripe should not reveal the PIN or any other PIN/authenticator pair. When a PIN is entered at a ATM (Automatic Teller Machine), it is encoded for comparison with the encoded representation on the magnetic stripe.
Password protection is yet another application of encryption techniques. Computers with password access control must represent the passwords in a database. It is desirable to encode the passwords because of possible exposure to operators, service personnel, systems programmers, etc. One-way transformations allow comparison of encoded passwords for authentication but inhibit obtaining of clear-text passwords from the encoded passwords.
Still another application of transformation technology is for accident protection. One-way transformations have been used in weapons program to protect data that might cause critical weapon functions to occur during an accident. The one-way nature of the transformation protects against accidental generation of functional data, while enabling checks of the functional data for accuracy.
A number of different transform techniques are known. Mathematical structure is important to assure unique transformations. Thus, polynomial transformations and matrix transformations provide one type of unique transformation. A common type is represented by transformations over what is known mathematically as a Galois field, denoted by GF(p). Such transformations are represented by mathematical functions, such as addition, multiplication or exponentiation, performed modulo the integer p, where p is a prime number or a power of a prime number.
Exclusive-or addition (modulo-2 addition) is used to provide a common implementation of a transformation over the field GF(2). A logical AND operation, equivalent to a modulo-2 multiplication, may be an associated transformation over the field GF(2), frequently used in combination with GF(2) addition.
Hardware implementation of each of these functions is well known. For example, GF(2) computations and transformations are well suited for implementation by available hardware. Such hardware is typically incorporated in microprocessor and computer devices, thus enabling computers to perform appropriate computations over the field GF(2).
Indeed, as shown in the following paragraphs, typical n-bit microprocessors and computers are inherently capable of performing non-unique transformations modulo 2.sup.n (although unique transformations over fields are more difficult).
For example, in a multiplication operation, when the multiplication results in more digits than the accumulator word length, the extra digits are stored in a carry register, storing a carry word denoted as c: EQU c=c.sub.n-1, c.sub.n-2, . . . , c.sub.o.
The numeric value of the carry word, n, is: EQU n.sub.c =2.sup.n (c.sub.n-1 2.sup.n-1 +c.sub.n-2 2.sup.n-2 + . . . +c.sub.o).sup.c =t(2.sup.n).
If the carry word were discarded, the value subtracted from the product would be n.sub.c, resulting in multiplication modulo 2.sup.n. Indeed, in an n-bit computer (having-n bit words) discarding the q most significant bits of a word, i.e., truncating the q most significant bits, results in a modulo 2.sup.n-q representation of the word.
An n-bit computer is thus inherently capable of providing straightforward modulo 2.sup.k representations of the data therein, for k=1, . . . , n.
However, it is frequently desirable to obtain a more complex encryption than is available in the field GF(2). Indeed, it is desirable to obtain modulo-p transforms of data, wherein p is preferably a prime number. However, with the exception of the trivial case p=2, it is generally appreciated that substantial difficulty is associated with obtaining modulo-p transformations where p is a prime number.
It is accordingly an object of the present invention to overcome the difficulties of the prior art and to provide method and apparatus for obtaining a representation of data modulo a prime number which is not much more difficult than representing the data modulo a power of 2.
It is also an object of the invention to provide method and apparatus for efficient transformation of data over a Galois field GF(p) where p is not necessarily a power of 2.
It is a more specific object of the invention to provide an efficient method and apparatus for encryption of data by transformation over a Galois field GF(p) where p is a prime number.
Another object of the invention is the provision of method and apparatus for obtaining products of two or more numbers modulo a prime number.
Still an additional object of the invention is the provision of method and apparatus for exponentiation of two or more numbers modulo a prime number.
It is a further object of the invention to overcome an inherent mismatch between microprocessor computations and residue algebra involving modulo arithmetic and more specifically to obtain a residue modulo p for products obtained by multiplication in an n-bit processor, where p is not equal to a power of 2.
Other objects, features and advantages of the present invention will become readily apparent to those skilled in the art from the following description wherein there is shown and described a preferred embodiment of the invention, simply by way of illustration and not of limitation of one of the best modes (and alternative embodiments) suited to carry out the invention. As will be realized upon examination of the specification and from practice of the same, the present invention is capable of still other, different, embodiments and its several details are capable of modifications in various obvious aspects, all without departing from the invention. Accordingly, the drawings and the descriptions provided herein are to be regarded as illustrative in nature and not as restrictive of the invention.